class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        return max(nums[0]+rob1(2,n-2,nums),rob1(1,n-1,nums));
        //如果第一个选，那么最后一个和第二个就不能选，相当于在第三个到倒数第二个做一次打家劫舍并加上第一个
        //如果第一个不选，那么就相当于在第二个到最后一个做一次打家劫舍
    }
    int rob1(int start,int end,vector<int>& nums){
        if(start>end)return 0;//可处理n==0或n==1的情况
        vector<int>f(end+1);
        auto g=f;
        f[0]=start==0?nums[0]:0;
        for(int i=start;i<=end;i++){
            f[i]=g[i-1]+nums[i];
            g[i]=max(f[i-1],g[i-1]);
        }
        return max(f[end],g[end]);
    }
};
